A logic simulator, a device using software to simulate the activity of a logic circuit, makes it possible to evaluate the performance of a circuit without building it. For example, the feasibility of a design may be verified by simulation in order to check that the correct logic functions are performed and to locate any timing problems. Simulation also will enable the performance of a circuit under fault conditions to be examined.
As circuit designs continue to grow in size and complexity, so do the demands placed upon logic simulators. To keep pace, work has been done to improve the basic performance of them. In so-called "event driven simulation", inputs to a computer primarily comprise a circuit representation, input stimuli and signal watch commands. For a description of fundamental event driven simulation, see Smith et al., "DEMAND DRIVEN SIMULATION: BACKSIM", 24th ACM/IEEE Design Automation Conference, Paper 11.1 (1987), pages 181-187 at 182. Processing tends to move from gate inputs to outputs and then onto the fan-out inputs driven by these outputs, always monotonically forward in time.
Types of event driven simulation include the "selective event method" and a "processing semantics description", described in Inagaki et al., "SIM/D: A LOGIC SIMULATOR FOR HIERARCHICAL DIGITAL SYSTEM CONTAINING LSI'S", Jyohousyori Gakki Ronbunshi Volume 12, No. 4 (1980), pages 332-339. The selective event method is an improvement on selective trace techniques which evaluate gates when input values to them are changed. The selective event method watches not only changes of inputs to each gate but also changes of output, and evaluates the gates only when the output as well as input values change. In the processing semantics description method of simulation, a circuit is classified into hierarchical modules, and evaluation is performed going back in time from the highest order module to the lowest order module or modules that are activated.
Conventional event driven logic simulation is disadvantageous in that it is able only to avoid processing of some of the gates and modules comprising a circuit, that is, the ones to which there is a change in input but not in output. The processing semantics description technique is disadvantageous in that it requires a considerable amount of effort for dividing logic circuitry into modules and for assigning to each module its position in the hierarchy.
Logic simulation generally is carried out by a general purpose computer programmed to execute logic simulation software. Such a computer is shown schematically in FIG. 1 as comprising a central processing unit (CPU) 20 receiving all logic simulation inputs through a keyboard 22 and supplying outputs to a display 24 and printer 26. In some logic simulation systems, an additional input representing actual device characteristics may be supplied to the CPU 20 from an optional pod 28, housing a physical logic device. The system further includes a random access memory 30 for storing data and programming temporarily and, optionally, a non-volatile memory, such as EPROM 32, for storing firmware which may include instructions for executing a simulation algorithm.
An example showing how logic simulation is implemented in accordance with the prior art is given in FIG. 2 for a circuit 300 shown in FIG. 3. Each of the logic elements forming the circuit shown in FIG. 3 is characterized as having an internal delay d1-d6. In this example, inverter 301 is considered to have a delay value d1 of 3 delay units. Inverter 305 has a delay value d5 of 1 delay unit and gate 302 has a delay value d2 of 5 units. Gate 304 has a delay value d4 of 5 and gate 303 a delay value d3 of 2. The circuit 300 comprises input signal lines (1), (7), (8) and (9) and an output line (101a) at the Q output of a D-type flip-flop 101. To the D-input of flip-flop 101 and the output of OR gate 303 is connected a signal line (2). To one input of gate 303 is connected a signal line (3) supplied by the output of an AND gate 302. Another output, from AND gate 304, is connected to the other input of OR gate 303 through signal line (4). One input to AND gate 302 is connected to the output of an inverter 305 through signal line (5). The other input to AND gate 302 is connected to the output of inverter 301 through signal line (6). The AND gate 304 has one input connected to input signal line (7) and to the input of inverter 305. The other input of gate 304 is connected to input signal line (9). Input signal line (1) is supplied to a clock terminal T of flip-flop 101.
Operating characteristics of a logic circuit simulation frequently are described with reference to a so-called "time-wheel". See, for example, Ulrich et al., "TECHNIQUES FOR LOGIC AND FAULT SIMULATION", VLSI System Design, October 1986, pages 68-81. A time-wheel depicts scheduled events at a fixed CPU time per event, regardless of the number of events already scheduled. A time-wheel 306 corresponding to the circuit of FIG. 3 is shown in FIG. 2. It consists of "time slots" 1 . . . 15 corresponding to 16 counts of a system clock (not shown). Events depicted as blocks 307-316 correspond to signal changes as they occur during operation of circuit 300 in response to the input signals shown.
Assume that signals applied to input signal lines (1), (7), (8) and (9) initially are at logic states 0, 0, 1, 0, respectively, and that the signal on input signal line (1) is to be changed from a 0 to a 1 at time t=15. As is characteristic of a D-type flip-flop, the Q output of the flip-flop stores the input signal state applied to terminal D in response to the signal change at input line 1 connected to the clock terminal T of the flip-flop.
Initially, at time slot t=0 on the wheel, events 307, 308, 309 and 310, i.e., the initial input signal states 0, 0, 1, 0, are registered as shown. The gate 305 is simulated by event 308, and then the event 311 is registered at time slot t=1 since the delay d5 for gate 305 is 1. Also at time slot t=0, the gate 301 is simulated by the event 309. Event 312 is registered at time slot t=3 since the delay d1 for gate 301 is 3. Similarly, gate 304 is simulated by events 310 and 308, and the event 313 is registered at time slot t=5 since the delay associated with gate 304 is d4=5.
Gate 101 is simulated by event 307 at time slot t =0, but no new event is produced since there is no change in the output of gate 101 at the first transition of the system clock.
After fetching and processing all the time slot t=0 events, the time slot t=1 events are processed. Gate 302 is simulated by event 311, and when the signal on line (3) is attempted to be scheduled to have a particular value at time slot t=2 according to d2=5 delay units, no event is produced because the initial value of the signal on line (3) is at the same value.
After the processing for time slot t=1 is completed, events at time slot t=2 on the wheel 306 are processed. However, since nothing is scheduled at time slot t=2, the processing steps automatically to time slot t=3. At time slot t=3 on the wheel, gate 302 is simulated by event 312, and event 314 is registered at time slot t=8; this follows expiration of delays of 3 and 5 units, respectively, corresponding to inverter 301 and gate 302.
When processing associated with time slot t=3 is completed, time slot t=5 is processed. The gate 303 is simulated by event 313. However, since the initial value of the signal on line (3) remains unchanged, and the output of the gate is also unchanged, no event is produced.
Following processing associated with time slot t=5, time slot t=8 is processed. Gate 303 is simulated by event 314, and event 315 is registered at time slot t=10 corresponding to delays associated with inverter 301 and gates 302 and 303. Following processing at time slot t=10, simulated of gate 101 is attempted by event 315. However, since no output change of gate 101 occurs, because there has been no change of signal at the input line (1), no event is produced. Instead, gate 101 is simulated by event 316 at time slot t=15, when the signal on line (1) changes from 0 to 1. Input 0 is produced at the Q terminal at the output of flip-flop (101) following a time delay corresponding to d6.
Thus, based upon the circuitry shown in FIG. 3, using conventional simulation it is necessary to register and simulate ten different events. This requires a considerable amount of processing, and represents a limitation to the speed at which simulation can be carried out.